home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / mozilla-firefox / include / js / jsdhash.h < prev    next >
C/C++ Source or Header  |  2006-05-08  |  25KB  |  580 lines
  1. /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
  2. /* ***** BEGIN LICENSE BLOCK *****
  3.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  4.  *
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at
  8.  * http://www.mozilla.org/MPL/
  9.  *
  10.  * Software distributed under the License is distributed on an "AS IS" basis,
  11.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12.  * for the specific language governing rights and limitations under the
  13.  * License.
  14.  *
  15.  * The Original Code is Mozilla JavaScript code.
  16.  *
  17.  * The Initial Developer of the Original Code is
  18.  * Netscape Communications Corporation.
  19.  * Portions created by the Initial Developer are Copyright (C) 1999-2001
  20.  * the Initial Developer. All Rights Reserved.
  21.  *
  22.  * Contributor(s):
  23.  *   Brendan Eich <brendan@mozilla.org> (Original Author)
  24.  *
  25.  * Alternatively, the contents of this file may be used under the terms of
  26.  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27.  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28.  * in which case the provisions of the GPL or the LGPL are applicable instead
  29.  * of those above. If you wish to allow use of your version of this file only
  30.  * under the terms of either the GPL or the LGPL, and not to allow others to
  31.  * use your version of this file under the terms of the MPL, indicate your
  32.  * decision by deleting the provisions above and replace them with the notice
  33.  * and other provisions required by the GPL or the LGPL. If you do not delete
  34.  * the provisions above, a recipient may use your version of this file under
  35.  * the terms of any one of the MPL, the GPL or the LGPL.
  36.  *
  37.  * ***** END LICENSE BLOCK ***** */
  38.  
  39. #ifndef jsdhash_h___
  40. #define jsdhash_h___
  41. /*
  42.  * Double hashing, a la Knuth 6.
  43.  */
  44. #include "jstypes.h"
  45.  
  46. JS_BEGIN_EXTERN_C
  47.  
  48. #if defined(__GNUC__) && defined(__i386__) && (__GNUC__ >= 3) && !defined(XP_OS2)
  49. #define JS_DHASH_FASTCALL __attribute__ ((regparm (3),stdcall))
  50. #else
  51. #define JS_DHASH_FASTCALL
  52. #endif
  53.  
  54. #ifdef DEBUG_XXXbrendan
  55. #define JS_DHASHMETER 1
  56. #endif
  57.  
  58. /* Table size limit, do not equal or exceed (see min&maxAlphaFrac, below). */
  59. #undef JS_DHASH_SIZE_LIMIT
  60. #define JS_DHASH_SIZE_LIMIT     JS_BIT(24)
  61.  
  62. /* Minimum table size, or gross entry count (net is at most .75 loaded). */
  63. #ifndef JS_DHASH_MIN_SIZE
  64. #define JS_DHASH_MIN_SIZE 16
  65. #elif (JS_DHASH_MIN_SIZE & (JS_DHASH_MIN_SIZE - 1)) != 0
  66. #error "JS_DHASH_MIN_SIZE must be a power of two!"
  67. #endif
  68.  
  69. /*
  70.  * Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
  71.  * expressed as a fixed-point 32-bit fraction.
  72.  */
  73. #define JS_DHASH_BITS           32
  74. #define JS_DHASH_GOLDEN_RATIO   0x9E3779B9U
  75.  
  76. /* Primitive and forward-struct typedefs. */
  77. typedef uint32                  JSDHashNumber;
  78. typedef struct JSDHashEntryHdr  JSDHashEntryHdr;
  79. typedef struct JSDHashEntryStub JSDHashEntryStub;
  80. typedef struct JSDHashTable     JSDHashTable;
  81. typedef struct JSDHashTableOps  JSDHashTableOps;
  82.  
  83. /*
  84.  * Table entry header structure.
  85.  *
  86.  * In order to allow in-line allocation of key and value, we do not declare
  87.  * either here.  Instead, the API uses const void *key as a formal parameter,
  88.  * and asks each entry for its key when necessary via a getKey callback, used
  89.  * when growing or shrinking the table.  Other callback types are defined
  90.  * below and grouped into the JSDHashTableOps structure, for single static
  91.  * initialization per hash table sub-type.
  92.  *
  93.  * Each hash table sub-type should nest the JSDHashEntryHdr structure at the
  94.  * front of its particular entry type.  The keyHash member contains the result
  95.  * of multiplying the hash code returned from the hashKey callback (see below)
  96.  * by JS_DHASH_GOLDEN_RATIO, then constraining the result to avoid the magic 0
  97.  * and 1 values.  The stored keyHash value is table size invariant, and it is
  98.  * maintained automatically by JS_DHashTableOperate -- users should never set
  99.  * it, and its only uses should be via the entry macros below.
  100.  *
  101.  * The JS_DHASH_ENTRY_IS_LIVE macro tests whether entry is neither free nor
  102.  * removed.  An entry may be either busy or free; if busy, it may be live or
  103.  * removed.  Consumers of this API should not access members of entries that
  104.  * are not live.
  105.  *
  106.  * However, use JS_DHASH_ENTRY_IS_BUSY for faster liveness testing of entries
  107.  * returned by JS_DHashTableOperate, as JS_DHashTableOperate never returns a
  108.  * non-live, busy (i.e., removed) entry pointer to its caller.  See below for
  109.  * more details on JS_DHashTableOperate's calling rules.
  110.  */
  111. struct JSDHashEntryHdr {
  112.     JSDHashNumber       keyHash;        /* every entry must begin like this */
  113. };
  114.  
  115. #define JS_DHASH_ENTRY_IS_FREE(entry)   ((entry)->keyHash == 0)
  116. #define JS_DHASH_ENTRY_IS_BUSY(entry)   (!JS_DHASH_ENTRY_IS_FREE(entry))
  117. #define JS_DHASH_ENTRY_IS_LIVE(entry)   ((entry)->keyHash >= 2)
  118.  
  119. /*
  120.  * A JSDHashTable is currently 8 words (without the JS_DHASHMETER overhead)
  121.  * on most architectures, and may be allocated on the stack or within another
  122.  * structure or class (see below for the Init and Finish functions to use).
  123.  *
  124.  * To decide whether to use double hashing vs. chaining, we need to develop a
  125.  * trade-off relation, as follows:
  126.  *
  127.  * Let alpha be the load factor, esize the entry size in words, count the
  128.  * entry count, and pow2 the power-of-two table size in entries.
  129.  *
  130.  *   (JSDHashTable overhead)    > (JSHashTable overhead)
  131.  *   (unused table entry space) > (malloc and .next overhead per entry) +
  132.  *                                (buckets overhead)
  133.  *   (1 - alpha) * esize * pow2 > 2 * count + pow2
  134.  *
  135.  * Notice that alpha is by definition (count / pow2):
  136.  *
  137.  *   (1 - alpha) * esize * pow2 > 2 * alpha * pow2 + pow2
  138.  *   (1 - alpha) * esize        > 2 * alpha + 1
  139.  *
  140.  *   esize > (1 + 2 * alpha) / (1 - alpha)
  141.  *
  142.  * This assumes both tables must keep keyHash, key, and value for each entry,
  143.  * where key and value point to separately allocated strings or structures.
  144.  * If key and value can be combined into one pointer, then the trade-off is:
  145.  *
  146.  *   esize > (1 + 3 * alpha) / (1 - alpha)
  147.  *
  148.  * If the entry value can be a subtype of JSDHashEntryHdr, rather than a type
  149.  * that must be allocated separately and referenced by an entry.value pointer
  150.  * member, and provided key's allocation can be fused with its entry's, then
  151.  * k (the words wasted per entry with chaining) is 4.
  152.  *
  153.  * To see these curves, feed gnuplot input like so:
  154.  *
  155.  *   gnuplot> f(x,k) = (1 + k * x) / (1 - x)
  156.  *   gnuplot> plot [0:.75] f(x,2), f(x,3), f(x,4)
  157.  *
  158.  * For k of 2 and a well-loaded table (alpha > .5), esize must be more than 4
  159.  * words for chaining to be more space-efficient than double hashing.
  160.  *
  161.  * Solving for alpha helps us decide when to shrink an underloaded table:
  162.  *
  163.  *   esize                     > (1 + k * alpha) / (1 - alpha)
  164.  *   esize - alpha * esize     > 1 + k * alpha
  165.  *   esize - 1                 > (k + esize) * alpha
  166.  *   (esize - 1) / (k + esize) > alpha
  167.  *
  168.  *   alpha < (esize - 1) / (esize + k)
  169.  *
  170.  * Therefore double hashing should keep alpha >= (esize - 1) / (esize + k),
  171.  * assuming esize is not too large (in which case, chaining should probably be
  172.  * used for any alpha).  For esize=2 and k=3, we want alpha >= .2; for esize=3
  173.  * and k=2, we want alpha >= .4.  For k=4, esize could be 6, and alpha >= .5
  174.  * would still obtain.  See the JS_DHASH_MIN_ALPHA macro further below.
  175.  *
  176.  * The current implementation uses a configurable lower bound on alpha, which
  177.  * defaults to .25, when deciding to shrink the table (while still respecting
  178.  * JS_DHASH_MIN_SIZE).
  179.  *
  180.  * Note a qualitative difference between chaining and double hashing: under
  181.  * chaining, entry addresses are stable across table shrinks and grows.  With
  182.  * double hashing, you can't safely hold an entry pointer and use it after an
  183.  * ADD or REMOVE operation, unless you sample table->generation before adding
  184.  * or removing, and compare the sample after, dereferencing the entry pointer
  185.  * only if table->generation has not changed.
  186.  *
  187.  * The moral of this story: there is no one-size-fits-all hash table scheme,
  188.  * but for small table entry size, and assuming entry address stability is not
  189.  * required, double hashing wins.
  190.  */
  191. struct JSDHashTable {
  192.     const JSDHashTableOps *ops;         /* virtual operations, see below */
  193.     void                *data;          /* ops- and instance-specific data */
  194.     int16               hashShift;      /* multiplicative hash shift */
  195.     uint8               maxAlphaFrac;   /* 8-bit fixed point max alpha */
  196.     uint8               minAlphaFrac;   /* 8-bit fixed point min alpha */
  197.     uint32              entrySize;      /* number of bytes in an entry */
  198.     uint32              entryCount;     /* number of entries in table */
  199.     uint32              removedCount;   /* removed entry sentinels in table */
  200.     uint32              generation;     /* entry storage generation number */
  201.     char                *entryStore;    /* entry storage */
  202. #ifdef JS_DHASHMETER
  203.     struct JSDHashStats {
  204.         uint32          searches;       /* total number of table searches */
  205.         uint32          steps;          /* hash chain links traversed */
  206.         uint32          hits;           /* searches that found key */
  207.         uint32          misses;         /* searches that didn't find key */
  208.         uint32          lookups;        /* number of JS_DHASH_LOOKUPs */
  209.         uint32          addMisses;      /* adds that miss, and do work */
  210.         uint32          addOverRemoved; /* adds that recycled a removed entry */
  211.         uint32          addHits;        /* adds that hit an existing entry */
  212.         uint32          addFailures;    /* out-of-memory during add growth */
  213.         uint32          removeHits;     /* removes that hit, and do work */
  214.         uint32          removeMisses;   /* useless removes that miss */
  215.         uint32          removeFrees;    /* removes that freed entry directly */
  216.         uint32          removeEnums;    /* removes done by Enumerate */
  217.         uint32          grows;          /* table expansions */
  218.         uint32          shrinks;        /* table contractions */
  219.         uint32          compresses;     /* table compressions */
  220.         uint32          enumShrinks;    /* contractions after Enumerate */
  221.     } stats;
  222. #endif
  223. };
  224.  
  225. /*
  226.  * Size in entries (gross, not net of free and removed sentinels) for table.
  227.  * We store hashShift rather than sizeLog2 to optimize the collision-free case
  228.  * in SearchTable.
  229.  */
  230. #define JS_DHASH_TABLE_SIZE(table)  JS_BIT(JS_DHASH_BITS - (table)->hashShift)
  231.  
  232. /*
  233.  * Table space at entryStore is allocated and freed using these callbacks.
  234.  * The allocator should return null on error only (not if called with nbytes
  235.  * equal to 0; but note that jsdhash.c code will never call with 0 nbytes).
  236.  */
  237. typedef void *
  238. (* JS_DLL_CALLBACK JSDHashAllocTable)(JSDHashTable *table, uint32 nbytes);
  239.  
  240. typedef void
  241. (* JS_DLL_CALLBACK JSDHashFreeTable) (JSDHashTable *table, void *ptr);
  242.  
  243. /*
  244.  * When a table grows or shrinks, each entry is queried for its key using this
  245.  * callback.  NB: in that event, entry is not in table any longer; it's in the
  246.  * old entryStore vector, which is due to be freed once all entries have been
  247.  * moved via moveEntry callbacks.
  248.  */
  249. typedef const void *
  250. (* JS_DLL_CALLBACK JSDHashGetKey)    (JSDHashTable *table,
  251.                                       JSDHashEntryHdr *entry);
  252.  
  253. /*
  254.  * Compute the hash code for a given key to be looked up, added, or removed
  255.  * from table.  A hash code may have any JSDHashNumber value.
  256.  */
  257. typedef JSDHashNumber
  258. (* JS_DLL_CALLBACK JSDHashHashKey)   (JSDHashTable *table, const void *key);
  259.  
  260. /*
  261.  * Compare the key identifying entry in table with the provided key parameter.
  262.  * Return JS_TRUE if keys match, JS_FALSE otherwise.
  263.  */
  264. typedef JSBool
  265. (* JS_DLL_CALLBACK JSDHashMatchEntry)(JSDHashTable *table,
  266.                                       const JSDHashEntryHdr *entry,
  267.                                       const void *key);
  268.  
  269. /*
  270.  * Copy the data starting at from to the new entry storage at to.  Do not add
  271.  * reference counts for any strong references in the entry, however, as this
  272.  * is a "move" operation: the old entry storage at from will be freed without
  273.  * any reference-decrementing callback shortly.
  274.  */
  275. typedef void
  276. (* JS_DLL_CALLBACK JSDHashMoveEntry)(JSDHashTable *table,
  277.                                      const JSDHashEntryHdr *from,
  278.                                      JSDHashEntryHdr *to);
  279.  
  280. /*
  281.  * Clear the entry and drop any strong references it holds.  This callback is
  282.  * invoked during a JS_DHASH_REMOVE operation (see below for operation codes),
  283.  * but only if the given key is found in the table.
  284.  */
  285. typedef void
  286. (* JS_DLL_CALLBACK JSDHashClearEntry)(JSDHashTable *table,
  287.                                       JSDHashEntryHdr *entry);
  288.  
  289. /*
  290.  * Called when a table (whether allocated dynamically by itself, or nested in
  291.  * a larger structure, or allocated on the stack) is finished.  This callback
  292.  * allows table->ops-specific code to finalize table->data.
  293.  */
  294. typedef void
  295. (* JS_DLL_CALLBACK JSDHashFinalize)  (JSDHashTable *table);
  296.  
  297. /*
  298.  * Initialize a new entry, apart from keyHash.  This function is called when
  299.  * JS_DHashTableOperate's JS_DHASH_ADD case finds no existing entry for the
  300.  * given key, and must add a new one.  At that point, entry->keyHash is not
  301.  * set yet, to avoid claiming the last free entry in a severely overloaded
  302.  * table.
  303.  */
  304. typedef JSBool
  305. (* JS_DLL_CALLBACK JSDHashInitEntry)(JSDHashTable *table,
  306.                                      JSDHashEntryHdr *entry,
  307.                                      const void *key);
  308.  
  309. /*
  310.  * Finally, the "vtable" structure for JSDHashTable.  The first eight hooks
  311.  * must be provided by implementations; they're called unconditionally by the
  312.  * generic jsdhash.c code.  Hooks after these may be null.
  313.  *
  314.  * Summary of allocation-related hook usage with C++ placement new emphasis:
  315.  *  allocTable          Allocate raw bytes with malloc, no ctors run.
  316.  *  freeTable           Free raw bytes with free, no dtors run.
  317.  *  initEntry           Call placement new using default key-based ctor.
  318.  *                      Return JS_TRUE on success, JS_FALSE on error.
  319.  *  moveEntry           Call placement new using copy ctor, run dtor on old
  320.  *                      entry storage.
  321.  *  clearEntry          Run dtor on entry.
  322.  *  finalize            Stub unless table->data was initialized and needs to
  323.  *                      be finalized.
  324.  *
  325.  * Note the reason why initEntry is optional: the default hooks (stubs) clear
  326.  * entry storage:  On successful JS_DHashTableOperate(tbl, key, JS_DHASH_ADD),
  327.  * the returned entry pointer addresses an entry struct whose keyHash member
  328.  * has been set non-zero, but all other entry members are still clear (null).
  329.  * JS_DHASH_ADD callers can test such members to see whether the entry was
  330.  * newly created by the JS_DHASH_ADD call that just succeeded.  If placement
  331.  * new or similar initialization is required, define an initEntry hook.  Of
  332.  * course, the clearEntry hook must zero or null appropriately.
  333.  *
  334.  * XXX assumes 0 is null for pointer types.
  335.  */
  336. struct JSDHashTableOps {
  337.     /* Mandatory hooks.  All implementations must provide these. */
  338.     JSDHashAllocTable   allocTable;
  339.     JSDHashFreeTable    freeTable;
  340.     JSDHashGetKey       getKey;
  341.     JSDHashHashKey      hashKey;
  342.     JSDHashMatchEntry   matchEntry;
  343.     JSDHashMoveEntry    moveEntry;
  344.     JSDHashClearEntry   clearEntry;
  345.     JSDHashFinalize     finalize;
  346.  
  347.     /* Optional hooks start here.  If null, these are not called. */
  348.     JSDHashInitEntry    initEntry;
  349. };
  350.  
  351. /*
  352.  * Default implementations for the above ops.
  353.  */
  354. extern JS_PUBLIC_API(void *)
  355. JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes);
  356.  
  357. extern JS_PUBLIC_API(void)
  358. JS_DHashFreeTable(JSDHashTable *table, void *ptr);
  359.  
  360. extern JS_PUBLIC_API(JSDHashNumber)
  361. JS_DHashStringKey(JSDHashTable *table, const void *key);
  362.  
  363. /* A minimal entry contains a keyHash header and a void key pointer. */
  364. struct JSDHashEntryStub {
  365.     JSDHashEntryHdr hdr;
  366.     const void      *key;
  367. };
  368.  
  369. extern JS_PUBLIC_API(const void *)
  370. JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry);
  371.  
  372. extern JS_PUBLIC_API(JSDHashNumber)
  373. JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key);
  374.  
  375. extern JS_PUBLIC_API(JSBool)
  376. JS_DHashMatchEntryStub(JSDHashTable *table,
  377.                        const JSDHashEntryHdr *entry,
  378.                        const void *key);
  379.  
  380. extern JS_PUBLIC_API(JSBool)
  381. JS_DHashMatchStringKey(JSDHashTable *table,
  382.                        const JSDHashEntryHdr *entry,
  383.                        const void *key);
  384.  
  385. extern JS_PUBLIC_API(void)
  386. JS_DHashMoveEntryStub(JSDHashTable *table,
  387.                       const JSDHashEntryHdr *from,
  388.                       JSDHashEntryHdr *to);
  389.  
  390. extern JS_PUBLIC_API(void)
  391. JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry);
  392.  
  393. extern JS_PUBLIC_API(void)
  394. JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry);
  395.  
  396. extern JS_PUBLIC_API(void)
  397. JS_DHashFinalizeStub(JSDHashTable *table);
  398.  
  399. /*
  400.  * If you use JSDHashEntryStub or a subclass of it as your entry struct, and
  401.  * if your entries move via memcpy and clear via memset(0), you can use these
  402.  * stub operations.
  403.  */
  404. extern JS_PUBLIC_API(const JSDHashTableOps *)
  405. JS_DHashGetStubOps(void);
  406.  
  407. /*
  408.  * Dynamically allocate a new JSDHashTable using malloc, initialize it using
  409.  * JS_DHashTableInit, and return its address.  Return null on malloc failure.
  410.  * Note that the entry storage at table->entryStore will be allocated using
  411.  * the ops->allocTable callback.
  412.  */
  413. extern JS_PUBLIC_API(JSDHashTable *)
  414. JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
  415.                  uint32 capacity);
  416.  
  417. /*
  418.  * Finalize table's data, free its entry storage (via table->ops->freeTable),
  419.  * and return the memory starting at table to the malloc heap.
  420.  */
  421. extern JS_PUBLIC_API(void)
  422. JS_DHashTableDestroy(JSDHashTable *table);
  423.  
  424. /*
  425.  * Initialize table with ops, data, entrySize, and capacity.  Capacity is a
  426.  * guess for the smallest table size at which the table will usually be less
  427.  * than 75% loaded (the table will grow or shrink as needed; capacity serves
  428.  * only to avoid inevitable early growth from JS_DHASH_MIN_SIZE).
  429.  */
  430. extern JS_PUBLIC_API(JSBool)
  431. JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
  432.                   uint32 entrySize, uint32 capacity);
  433.  
  434. /*
  435.  * Set maximum and minimum alpha for table.  The defaults are 0.75 and .25.
  436.  * maxAlpha must be in [0.5, 0.9375] for the default JS_DHASH_MIN_SIZE; or if
  437.  * MinSize=JS_DHASH_MIN_SIZE <= 256, in [0.5, (float)(MinSize-1)/MinSize]; or
  438.  * else in [0.5, 255.0/256].  minAlpha must be in [0, maxAlpha / 2), so that
  439.  * we don't shrink on the very next remove after growing a table upon adding
  440.  * an entry that brings entryCount past maxAlpha * tableSize.
  441.  */
  442. extern JS_PUBLIC_API(void)
  443. JS_DHashTableSetAlphaBounds(JSDHashTable *table,
  444.                             float maxAlpha,
  445.                             float minAlpha);
  446.  
  447. /*
  448.  * Call this macro with k, the number of pointer-sized words wasted per entry
  449.  * under chaining, to compute the minimum alpha at which double hashing still
  450.  * beats chaining.
  451.  */
  452. #define JS_DHASH_MIN_ALPHA(table, k)                                          \
  453.     ((float)((table)->entrySize / sizeof(void *) - 1)                         \
  454.      / ((table)->entrySize / sizeof(void *) + (k)))
  455.  
  456. /*
  457.  * Finalize table's data, free its entry storage using table->ops->freeTable,
  458.  * and leave its members unchanged from their last live values (which leaves
  459.  * pointers dangling).  If you want to burn cycles clearing table, it's up to
  460.  * your code to call memset.
  461.  */
  462. extern JS_PUBLIC_API(void)
  463. JS_DHashTableFinish(JSDHashTable *table);
  464.  
  465. /*
  466.  * To consolidate keyHash computation and table grow/shrink code, we use a
  467.  * single entry point for lookup, add, and remove operations.  The operation
  468.  * codes are declared here, along with codes returned by JSDHashEnumerator
  469.  * functions, which control JS_DHashTableEnumerate's behavior.
  470.  */
  471. typedef enum JSDHashOperator {
  472.     JS_DHASH_LOOKUP = 0,        /* lookup entry */
  473.     JS_DHASH_ADD = 1,           /* add entry */
  474.     JS_DHASH_REMOVE = 2,        /* remove entry, or enumerator says remove */
  475.     JS_DHASH_NEXT = 0,          /* enumerator says continue */
  476.     JS_DHASH_STOP = 1           /* enumerator says stop */
  477. } JSDHashOperator;
  478.  
  479. /*
  480.  * To lookup a key in table, call:
  481.  *
  482.  *  entry = JS_DHashTableOperate(table, key, JS_DHASH_LOOKUP);
  483.  *
  484.  * If JS_DHASH_ENTRY_IS_BUSY(entry) is true, key was found and it identifies
  485.  * entry.  If JS_DHASH_ENTRY_IS_FREE(entry) is true, key was not found.
  486.  *
  487.  * To add an entry identified by key to table, call:
  488.  *
  489.  *  entry = JS_DHashTableOperate(table, key, JS_DHASH_ADD);
  490.  *
  491.  * If entry is null upon return, then either the table is severely overloaded,
  492.  * and memory can't be allocated for entry storage via table->ops->allocTable;
  493.  * Or if table->ops->initEntry is non-null, the table->ops->initEntry op may
  494.  * have returned false.
  495.  *
  496.  * Otherwise, entry->keyHash has been set so that JS_DHASH_ENTRY_IS_BUSY(entry)
  497.  * is true, and it is up to the caller to initialize the key and value parts
  498.  * of the entry sub-type, if they have not been set already (i.e. if entry was
  499.  * not already in the table, and if the optional initEntry hook was not used).
  500.  *
  501.  * To remove an entry identified by key from table, call:
  502.  *
  503.  *  (void) JS_DHashTableOperate(table, key, JS_DHASH_REMOVE);
  504.  *
  505.  * If key's entry is found, it is cleared (via table->ops->clearEntry) and
  506.  * the entry is marked so that JS_DHASH_ENTRY_IS_FREE(entry).  This operation
  507.  * returns null unconditionally; you should ignore its return value.
  508.  */
  509. extern JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
  510. JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op);
  511.  
  512. /*
  513.  * Remove an entry already accessed via LOOKUP or ADD.
  514.  *
  515.  * NB: this is a "raw" or low-level routine, intended to be used only where
  516.  * the inefficiency of a full JS_DHashTableOperate (which rehashes in order
  517.  * to find the entry given its key) is not tolerable.  This function does not
  518.  * shrink the table if it is underloaded.  It does not update stats #ifdef
  519.  * JS_DHASHMETER, either.
  520.  */
  521. extern JS_PUBLIC_API(void)
  522. JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry);
  523.  
  524. /*
  525.  * Enumerate entries in table using etor:
  526.  *
  527.  *   count = JS_DHashTableEnumerate(table, etor, arg);
  528.  *
  529.  * JS_DHashTableEnumerate calls etor like so:
  530.  *
  531.  *   op = etor(table, entry, number, arg);
  532.  *
  533.  * where number is a zero-based ordinal assigned to live entries according to
  534.  * their order in table->entryStore.
  535.  *
  536.  * The return value, op, is treated as a set of flags.  If op is JS_DHASH_NEXT,
  537.  * then continue enumerating.  If op contains JS_DHASH_REMOVE, then clear (via
  538.  * table->ops->clearEntry) and free entry.  Then we check whether op contains
  539.  * JS_DHASH_STOP; if so, stop enumerating and return the number of live entries
  540.  * that were enumerated so far.  Return the total number of live entries when
  541.  * enumeration completes normally.
  542.  *
  543.  * If etor calls JS_DHashTableOperate on table with op != JS_DHASH_LOOKUP, it
  544.  * must return JS_DHASH_STOP; otherwise undefined behavior results.
  545.  *
  546.  * If any enumerator returns JS_DHASH_REMOVE, table->entryStore may be shrunk
  547.  * or compressed after enumeration, but before JS_DHashTableEnumerate returns.
  548.  * Such an enumerator therefore can't safely set aside entry pointers, but an
  549.  * enumerator that never returns JS_DHASH_REMOVE can set pointers to entries
  550.  * aside, e.g., to avoid copying live entries into an array of the entry type.
  551.  * Copying entry pointers is cheaper, and safe so long as the caller of such a
  552.  * "stable" Enumerate doesn't use the set-aside pointers after any call either
  553.  * to PL_DHashTableOperate, or to an "unstable" form of Enumerate, which might
  554.  * grow or shrink entryStore.
  555.  *
  556.  * If your enumerator wants to remove certain entries, but set aside pointers
  557.  * to other entries that it retains, it can use JS_DHashTableRawRemove on the
  558.  * entries to be removed, returning JS_DHASH_NEXT to skip them.  Likewise, if
  559.  * you want to remove entries, but for some reason you do not want entryStore
  560.  * to be shrunk or compressed, you can call JS_DHashTableRawRemove safely on
  561.  * the entry being enumerated, rather than returning JS_DHASH_REMOVE.
  562.  */
  563. typedef JSDHashOperator
  564. (* JS_DLL_CALLBACK JSDHashEnumerator)(JSDHashTable *table, JSDHashEntryHdr *hdr,
  565.                                       uint32 number, void *arg);
  566.  
  567. extern JS_PUBLIC_API(uint32)
  568. JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg);
  569.  
  570. #ifdef JS_DHASHMETER
  571. #include <stdio.h>
  572.  
  573. extern JS_PUBLIC_API(void)
  574. JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp);
  575. #endif
  576.  
  577. JS_END_EXTERN_C
  578.  
  579. #endif /* jsdhash_h___ */
  580.